/* Copyright (c) 2013 Dropbox, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <limits>

#ifdef _MSC_VER
#define snprintf _snprintf
#endif

namespace cinatra
{

	static const int max_depth = 200;

	/* * * * * * * * * * * * * * * * * * * *
	 * Serialization
	 */

	inline static void dump(std::nullptr_t, std::string &out)
	{
		out += "null";
	}

	inline static void dump(double value, std::string &out)
	{
		char buf[32];
		snprintf(buf, sizeof buf, "%.17g", value);
		out += buf;
	}

	inline static void dump(int value, std::string &out) {
		char buf[32];
		snprintf(buf, sizeof buf, "%d", value);
		out += buf;
	}

	inline static void dump(bool value, std::string &out)
	{
		out += value ? "true" : "false";
	}

	inline static void dump(const std::string &value, std::string &out)
	{
		out += '"';
		for (size_t i = 0; i < value.length(); i++)
		{
			const char ch = value[i];
			if (ch == '\\')
			{
				out += "\\\\";
			}
			else if (ch == '"')
			{
				out += "\\\"";
			}
			else if (ch == '\b')
			{
				out += "\\b";
			}
			else if (ch == '\f')
			{
				out += "\\f";
			}
			else if (ch == '\n')
			{
				out += "\\n";
			}
			else if (ch == '\r')
			{
				out += "\\r";
			}
			else if (ch == '\t')
			{
				out += "\\t";
			}
			else if ((uint8_t)ch <= 0x1f)
			{
				char buf[8];
				snprintf(buf, sizeof buf, "\\u%04x", ch);
				out += buf;
			}
			else if ((uint8_t)ch == 0xe2 && (uint8_t)value[i + 1] == 0x80
				&& (uint8_t)value[i + 2] == 0xa8)
			{
				out += "\\u2028";
				i += 2;
			}
			else if ((uint8_t)ch == 0xe2 && (uint8_t)value[i + 1] == 0x80
				&& (uint8_t)value[i + 2] == 0xa9)
			{
				out += "\\u2029";
				i += 2;
			}
			else
			{
				out += ch;
			}
		}
		out += '"';
	}

	inline static void dump(const Json::array &values, std::string &out)
	{
		bool first = true;
		out += "[";
		for (auto &value : values)
		{
			if (!first)
				out += ", ";
			value.dump(out);
			first = false;
		}
		out += "]";
	}

	inline static void dump(const Json::object &values, std::string &out)
	{
		bool first = true;
		out += "{";
		for (const std::pair<std::string, Json> &kv : values)
		{
			if (!first)
				out += ", ";
			dump(kv.first, out);
			out += ": ";
			kv.second.dump(out);
			first = false;
		}
		out += "}";
	}

	void Json::dump(std::string &out) const
	{
		m_ptr->dump(out);
	}

	/* * * * * * * * * * * * * * * * * * * *
	 * Value wrappers
	 */

	template <Json::Type tag, typename T>
	class Value : public JsonValue
	{
	protected:

		// Constructors
		Value(const T &value) : m_value(value) {}
		Value(T &&value) : m_value(std::move(value)) {}

		// Get type tag
		Json::Type type() const
		{
			return tag;
		}

		// Comparisons
		bool equals(const JsonValue * other) const
		{
			return m_value == reinterpret_cast<const Value<tag, T> *>(other)->m_value;
		}
		bool less(const JsonValue * other) const
		{
			return m_value < reinterpret_cast<const Value<tag, T> *>(other)->m_value;
		}

		const T m_value;
		void dump(std::string &out) const { cinatra::dump(m_value, out); }
	};

	class JsonDouble final : public Value<Json::NUMBER, double>
	{
		double number_value() const { return m_value; }
		int int_value() const { return int(m_value); }
		bool equals(const JsonValue * other) const { return m_value == other->number_value(); }
		bool less(const JsonValue * other)   const { return m_value < other->number_value(); }
	public:
		JsonDouble(double value) : Value(value) {}
	};

	class JsonInt final : public Value<Json::NUMBER, int>
	{
		double number_value() const { return m_value; }
		int int_value() const { return m_value; }
		bool equals(const JsonValue * other) const { return m_value == other->number_value(); }
		bool less(const JsonValue * other)   const { return m_value < other->number_value(); }
	public:
		JsonInt(double value) : Value(int(value)) {}
	};

	class JsonBoolean final : public Value<Json::BOOL, bool>
	{
		bool bool_value() const { return m_value; }
	public:
		JsonBoolean(bool value) : Value(value) {}
	};

	class JsonString final : public Value<Json::STRING, std::string>
	{
		const std::string &string_value() const { return m_value; }
	public:
		JsonString(const std::string &value) : Value(value) {}
		JsonString(std::string &&value) : Value(std::move(value)) {}
	};

	class JsonArray final : public Value<Json::ARRAY, Json::array>
	{
		const Json::array &array_items() const { return m_value; }
		inline const Json & operator[](size_t i) const;
	public:
		JsonArray(const Json::array &value) : Value(value) {}
		JsonArray(Json::array &&value) : Value(std::move(value)) {}
	};

	class JsonObject final : public Value<Json::OBJECT, Json::object>
	{
		const Json::object &object_items() const { return m_value; }
		inline const Json & operator[](const std::string &key) const;
	public:
		JsonObject(const Json::object &value) : Value(value) {}
		JsonObject(Json::object &&value) : Value(std::move(value)) {}
	};

	class JsonNull final : public Value<Json::NUL, std::nullptr_t>
	{
	public:
		JsonNull() : Value(nullptr) {}
	};

	/* * * * * * * * * * * * * * * * * * * *
	 * Static globals - static-init-safe
	 */
	struct Statics
	{
		const std::shared_ptr<JsonValue> null = std::make_shared<JsonNull>();
		const std::shared_ptr<JsonValue> t = std::make_shared<JsonBoolean>(true);
		const std::shared_ptr<JsonValue> f = std::make_shared<JsonBoolean>(false);
		const std::string empty_string;
		const std::vector<Json> empty_vector;
		const std::map<std::string, Json> empty_map;
		Statics() {}
	};

	inline const Statics & statics()
	{
		static const Statics s{};
		return s;
	}

	inline const Json & static_null()
	{
		// This has to be separate, not in Statics, because Json() accesses statics().null.
		static const Json json_null;
		return json_null;
	}

	/* * * * * * * * * * * * * * * * * * * *
	 * Constructors
	 */

	Json::Json() JSON11_NOEXCEPT                  : m_ptr(statics().null) {}
	Json::Json(std::nullptr_t) JSON11_NOEXCEPT : m_ptr(statics().null) {}
	Json::Json(double value) : m_ptr(std::make_shared<JsonDouble>(value)) {}
	Json::Json(int value) : m_ptr(std::make_shared<JsonInt>(value)) {}
	Json::Json(bool value) : m_ptr(value ? statics().t : statics().f) {}
	Json::Json(const std::string &value) : m_ptr(std::make_shared<JsonString>(value)) {}
	Json::Json(std::string &&value) : m_ptr(std::make_shared<JsonString>(move(value))) {}
	Json::Json(const char * value) : m_ptr(std::make_shared<JsonString>(value)) {}
	Json::Json(const Json::array &values) : m_ptr(std::make_shared<JsonArray>(values)) {}
	Json::Json(Json::array &&values) : m_ptr(std::make_shared<JsonArray>(move(values))) {}
	Json::Json(const Json::object &values) : m_ptr(std::make_shared<JsonObject>(values)) {}
	Json::Json(Json::object &&values) : m_ptr(std::make_shared<JsonObject>(move(values))) {}

	/* * * * * * * * * * * * * * * * * * * *
	 * Accessors
	 */

	Json::Type Json::type()                           const { return m_ptr->type(); }
	double Json::number_value()                       const { return m_ptr->number_value(); }
	int Json::int_value()                             const { return m_ptr->int_value(); }
	bool Json::bool_value()                           const { return m_ptr->bool_value(); }
	const std::string & Json::string_value()               const { return m_ptr->string_value(); }
	const std::vector<Json> & Json::array_items()          const { return m_ptr->array_items(); }
	const std::map<std::string, Json> & Json::object_items()    const { return m_ptr->object_items(); }
	const Json & Json::operator[] (size_t i)          const { return (*m_ptr)[i]; }
	const Json & Json::operator[] (const std::string &key) const { return (*m_ptr)[key]; }

	double                    JsonValue::number_value()              const { return 0; }
	int                       JsonValue::int_value()                 const { return 0; }
	bool                      JsonValue::bool_value()                const { return false; }
	const std::string &            JsonValue::string_value()              const { return statics().empty_string; }
	const std::vector<Json> &      JsonValue::array_items()               const { return statics().empty_vector; }
	const std::map<std::string, Json> & JsonValue::object_items()              const { return statics().empty_map; }
	const Json &              JsonValue::operator[] (size_t)         const { return static_null(); }
	const Json &              JsonValue::operator[] (const std::string &) const { return static_null(); }

	const Json & JsonObject::operator[] (const std::string &key) const
	{
		auto iter = m_value.find(key);
		return (iter == m_value.end()) ? static_null() : iter->second;
	}
	const Json & JsonArray::operator[] (size_t i) const
	{
		if (i >= m_value.size()) return static_null();
		else return m_value[i];
	}

	/* * * * * * * * * * * * * * * * * * * *
	 * Comparison
	 */

	bool Json::operator== (const Json &other) const
	{
		if (m_ptr->type() != other.m_ptr->type())
			return false;

		return m_ptr->equals(other.m_ptr.get());
	}

	bool Json::operator< (const Json &other) const
	{
		if (m_ptr->type() != other.m_ptr->type())
			return m_ptr->type() < other.m_ptr->type();

		return m_ptr->less(other.m_ptr.get());
	}

	/* * * * * * * * * * * * * * * * * * * *
	 * Parsing
	 */

	/* esc(c)
	 *
	 * Format char c suitable for printing in an error message.
	 */
	static inline std::string esc(char c)
	{
		char buf[12];
		if ((uint8_t)c >= 0x20 && (uint8_t)c <= 0x7f)
		{
			snprintf(buf, sizeof buf, "'%c' (%d)", c, c);
		}
		else {
			snprintf(buf, sizeof buf, "(%d)", c);
		}
		return std::string(buf);
	}

	static inline bool in_range(long x, long lower, long upper)
	{
		return (x >= lower && x <= upper);
	}

	/* JsonParser
	 *
	 * Object that tracks all state of an in-progress parse.
	 */
	struct JsonParser
	{

		/* State
		 */
		const std::string &str;
		std::size_t i;
		std::string &err;
		bool failed;

		/* fail(msg, err_ret = Json())
		 *
		 * Mark this parse as failed.
		 */
		Json fail(std::string &&msg)
		{
			return fail(std::move(msg), Json());
		}

		template <typename T>
		T fail(std::string &&msg, const T err_ret)
		{
			if (!failed)
				err = std::move(msg);
			failed = true;
			return err_ret;
		}

		/* consume_whitespace()
		 *
		 * Advance until the current character is non-whitespace.
		 */
		void consume_whitespace()
		{
			while (str[i] == ' ' || str[i] == '\r' || str[i] == '\n' || str[i] == '\t')
				i++;
		}

		/* get_next_token()
		 *
		 * Return the next non-whitespace character. If the end of the input is reached,
		 * flag an error and return 0.
		 */
		char get_next_token()
		{
			consume_whitespace();
			if (i == str.size())
				return fail("unexpected end of input", 0);

			return str[i++];
		}

		/* encode_utf8(pt, out)
		 *
		 * Encode pt as UTF-8 and add it to out.
		 */
		void encode_utf8(long pt, std::string & out)
		{
			if (pt < 0)
				return;

			if (pt < 0x80)
			{
				out += char(pt);
			}
			else if (pt < 0x800)
			{
				out += char((pt >> 6) | 0xC0);
				out += (pt & 0x3F) | 0x80;
			}
			else if (pt < 0x10000)
			{
				out += char((pt >> 12) | 0xE0);
				out += ((pt >> 6) & 0x3F) | 0x80;
				out += (pt & 0x3F) | 0x80;
			}
			else
			{
				out += char((pt >> 18) | 0xF0);
				out += ((pt >> 12) & 0x3F) | 0x80;
				out += ((pt >> 6) & 0x3F) | 0x80;
				out += (pt & 0x3F) | 0x80;
			}
		}

		/* parse_string()
		 *
		 * Parse a string, starting at the current position.
		 */
		std::string parse_string()
		{
			std::string out;
			long last_escaped_codepoint = -1;
			while (true)
			{
				if (i == str.size())
					return fail("unexpected end of input in string", "");

				char ch = str[i++];

				if (ch == '"')
				{
					encode_utf8(last_escaped_codepoint, out);
					return out;
				}

				if (in_range(ch, 0, 0x1f))
					return fail("unescaped " + esc(ch) + " in string", "");

				// The usual case: non-escaped characters
				if (ch != '\\')
				{
					encode_utf8(last_escaped_codepoint, out);
					last_escaped_codepoint = -1;
					out += ch;
					continue;
				}

				// Handle escapes
				if (i == str.size())
					return fail("unexpected end of input in string", "");

				ch = str[i++];

				if (ch == 'u')
				{
					// Extract 4-byte escape sequence
					std::string esc = str.substr(i, 4);
					for (int j = 0; j < 4; j++)
					{
						if (!in_range(esc[j], 'a', 'f') && !in_range(esc[j], 'A', 'F')
							&& !in_range(esc[j], '0', '9'))
							return fail("bad \\u escape: " + esc, "");
					}

					long codepoint = strtol(esc.data(), nullptr, 16);

					// JSON specifies that characters outside the BMP shall be encoded as a pair
					// of 4-hex-digit \u escapes encoding their surrogate pair components. Check
					// whether we're in the middle of such a beast: the previous codepoint was an
					// escaped lead (high) surrogate, and this is a trail (low) surrogate.
					if (in_range(last_escaped_codepoint, 0xD800, 0xDBFF)
						&& in_range(codepoint, 0xDC00, 0xDFFF))
					{
						// Reassemble the two surrogate pairs into one astral-plane character, per
						// the UTF-16 algorithm.
						encode_utf8((((last_escaped_codepoint - 0xD800) << 10)
							| (codepoint - 0xDC00)) + 0x10000, out);
						last_escaped_codepoint = -1;
					}
					else
					{
						encode_utf8(last_escaped_codepoint, out);
						last_escaped_codepoint = codepoint;
					}

					i += 4;
					continue;
				}

				encode_utf8(last_escaped_codepoint, out);
				last_escaped_codepoint = -1;

				if (ch == 'b')
				{
					out += '\b';
				}
				else if (ch == 'f')
				{
					out += '\f';
				}
				else if (ch == 'n')
				{
					out += '\n';
				}
				else if (ch == 'r')
				{
					out += '\r';
				}
				else if (ch == 't')
				{
					out += '\t';
				}
				else if (ch == '"' || ch == '\\' || ch == '/')
				{
					out += ch;
				}
				else
				{
					return fail("invalid escape character " + esc(ch), "");
				}
			}
		}

		/* parse_number()
		 *
		 * Parse a double.
		 */
		Json parse_number()
		{
			size_t start_pos = i;

			if (str[i] == '-')
				i++;

			// Integer part
			if (str[i] == '0')
			{
				i++;
				if (in_range(str[i], '0', '9'))
					return fail("leading 0s not permitted in numbers");
			}
			else if (in_range(str[i], '1', '9'))
			{
				i++;
				while (in_range(str[i], '0', '9'))
					i++;
			}
			else
			{
				return fail("invalid " + esc(str[i]) + " in number");
			}

			if (str[i] != '.' && str[i] != 'e' && str[i] != 'E'
				&& (i - start_pos) <= (size_t)std::numeric_limits<int>::digits10)
			{
				return std::atoi(str.c_str() + start_pos);
			}

			// Decimal part
			if (str[i] == '.')
			{
				i++;
				if (!in_range(str[i], '0', '9'))
					return fail("at least one digit required in fractional part");

				while (in_range(str[i], '0', '9'))
					i++;
			}

			// Exponent part
			if (str[i] == 'e' || str[i] == 'E')
			{
				i++;

				if (str[i] == '+' || str[i] == '-')
					i++;

				if (!in_range(str[i], '0', '9'))
					return fail("at least one digit required in exponent");

				while (in_range(str[i], '0', '9'))
					i++;
			}

			return std::atof(str.c_str() + start_pos);
		}

		/* expect(str, res)
		 *
		 * Expect that 'str' starts at the character that was just read. If it does, advance
		 * the input and return res. If not, flag an error.
		 */
		Json expect(const std::string &expected, Json res)
		{
			assert(i != 0);
			i--;
			const std::string found = str.substr(i, expected.length());
			if (expected == found)
			{
				i += expected.length();
				return res;
			}
			else
			{
				return fail("parse error: expected " + expected + ", got " + found);
			}
		}

		/* parse_json()
		 *
		 * Parse a JSON object.
		 */
		Json parse_json(int depth)
		{
			if (depth > max_depth)
			{
				return fail("exceeded maximum nesting depth");
			}

			char ch = get_next_token();
			if (failed)
				return Json();

			if (ch == '-' || (ch >= '0' && ch <= '9'))
			{
				i--;
				return parse_number();
			}

			if (ch == 't')
				return expect("true", true);

			if (ch == 'f')
				return expect("false", false);

			if (ch == 'n')
				return expect("null", Json());

			if (ch == '"')
				return parse_string();

			if (ch == '{')
			{
				std::map<std::string, Json> data;
				ch = get_next_token();
				if (ch == '}')
					return data;

				while (1)
				{
					if (ch != '"')
						return fail("expected '\"' in object, got " + esc(ch));

					std::string key = parse_string();
					if (failed)
						return Json();

					ch = get_next_token();
					if (ch != ':')
						return fail("expected ':' in object, got " + esc(ch));

					data[std::move(key)] = parse_json(depth + 1);
					if (failed)
						return Json();

					ch = get_next_token();
					if (ch == '}')
						break;
					if (ch != ',')
						return fail("expected ',' in object, got " + esc(ch));

					ch = get_next_token();
				}
				return data;
			}

			if (ch == '[')
			{
				std::vector<Json> data;
				ch = get_next_token();
				if (ch == ']')
					return data;

				while (1)
				{
					i--;
					data.push_back(parse_json(depth + 1));
					if (failed)
						return Json();

					ch = get_next_token();
					if (ch == ']')
						break;
					if (ch != ',')
						return fail("expected ',' in list, got " + esc(ch));

					ch = get_next_token();
					(void)ch;
				}
				return data;
			}

			return fail("expected value, got " + esc(ch));
		}
	};

	Json Json::parse(const std::string &in, std::string &err)
	{
		JsonParser parser{ in, 0, err, false };
		Json result = parser.parse_json(0);

		// Check for any trailing garbage
		parser.consume_whitespace();
		if (parser.i != in.size())
			return parser.fail("unexpected trailing " + esc(in[parser.i]));

		return result;
	}

	// Documented in json11.hpp
	std::vector<Json> Json::parse_multi(const std::string &in, std::string &err)
	{
		JsonParser parser{ in, 0, err, false };

		std::vector<Json> json_vec;
		while (parser.i != in.size() && !parser.failed) {
			json_vec.push_back(parser.parse_json(0));
			// Check for another object
			parser.consume_whitespace();
		}
		return json_vec;
	}

	/* * * * * * * * * * * * * * * * * * * *
	 * Shape-checking
	 */

	bool Json::has_shape(const shape & types, std::string & err) const
	{
		if (!is_object())
		{
			err = "expected JSON object, got " + dump();
			return false;
		}

		for (auto & item : types)
		{
			if ((*this)[item.first].type() != item.second)
			{
				err = "bad type for " + item.first + " in " + dump();
				return false;
			}
		}

		return true;
	}

}

#ifdef _MSC_VER
#undef snprintf
#endif
